\chapter{流密码(stream ciphers)}
利用密钥产生一个密钥流，利用密钥流对数据流进行加密。密钥流和数据流，这个流是什么意思？流（stream）从直观上来讲，应该是一种一个接着一个的运动方式。一个接着一个，这个“个”是什么？应该是一个最小单位，比如“人流”，这个“个”就是人，“水流”“泥石流”这个单位就不太好确定，与研究者的研究粒度和方法有关。\par
我们看看下面的一段文字(65个字符，包含标点符号)：\par

\begin{lstlisting}
  这是一门网络空间安全学科的基础课，是信息安全专业的一门专业基础课，
  学生通过学习这门课要理解加解密的基本原理，掌握基本的加解密方法。
\end{lstlisting}
\par

   这些文字存成纯文本模式（想想这个含义是什么？），共有占195个字节(我的计算机是MacBook，我查看存储的txt文件，文件占用了4k的磁盘空间，想想为什么？)，简单计算可知一个字符占3个字节，用十六进制显示为：\par
   
\begin{lstlisting}
  E8BF99 E698AF E4B880 E997A8 E7BD91 E7BB9C E7A9BA E997B4 E5AE89 E585A8
  E5ADA6 E7A791 E79A84 E59FBA E7A180 E8AFBE EFBC8C E698AF E4BFA1 E681AF 
  E5AE89 E585A8 E4B893 E4B89A E79A84 E4B880 E997A8 E4B893 E4B89A E59FBA 
  E7A180 E8AFBE EFBC8C E5ADA6 E7949F E9809A E8BF87 E5ADA6 E4B9A0 E8BF99 
  E997A8 E8AFBE E8A681 E79086 E8A7A3 E58AA0 E8A7A3 E5AF86 E79A84 E59FBA 
  E69CAC E58E9F E79086 EFBC8C E68E8C E68FA1 E59FBA E69CAC E79A84 E58AA0 
  E8A7A3 E5AF86 E696B9 E6B395 E38082
\end{lstlisting}
\par
同样把这段信息以二进制编码的方式显示：\par
\begin{lstlisting}
0000000: 11101000 10111111 10011001 11100110 10011000 10101111  ......
00000006: 11100100 10111000 10000000 11101001 10010111 10101000  ......
0000000c: 11100111 10111101 10010001 11100111 10111011 10011100  ......
00000012: 11100111 10101001 10111010 11101001 10010111 10110100  ......
00000018: 11100101 10101110 10001001 11100101 10000101 10101000  ......
0000001e: 11100101 10101101 10100110 11100111 10100111 10010001  ......
00000024: 11100111 10011010 10000100 11100101 10011111 10111010  ......
0000002a: 11100111 10100001 10000000 11101000 10101111 10111110  ......
00000030: 11101111 10111100 10001100 11100110 10011000 10101111  ......
00000036: 11100100 10111111 10100001 11100110 10000001 10101111  ......
0000003c: 11100101 10101110 10001001 11100101 10000101 10101000  ......
00000042: 11100100 10111000 10010011 11100100 10111000 10011010  ......
00000048: 11100111 10011010 10000100 11100100 10111000 10000000  ......
0000004e: 11101001 10010111 10101000 11100100 10111000 10010011  ......
00000054: 11100100 10111000 10011010 11100101 10011111 10111010  ......
0000005a: 11100111 10100001 10000000 11101000 10101111 10111110  ......
00000060: 11101111 10111100 10001100 11100101 10101101 10100110  ......
00000066: 11100111 10010100 10011111 11101001 10000000 10011010  ......
0000006c: 11101000 10111111 10000111 11100101 10101101 10100110  ......
00000072: 11100100 10111001 10100000 11101000 10111111 10011001  ......
00000078: 11101001 10010111 10101000 11101000 10101111 10111110  ......
0000007e: 11101000 10100110 10000001 11100111 10010000 10000110  ......
00000084: 11101000 10100111 10100011 11100101 10001010 10100000  ......
0000008a: 11101000 10100111 10100011 11100101 10101111 10000110  ......
00000090: 11100111 10011010 10000100 11100101 10011111 10111010  ......
00000096: 11100110 10011100 10101100 11100101 10001110 10011111  ......
0000009c: 11100111 10010000 10000110 11101111 10111100 10001100  ......
000000a2: 11100110 10001110 10001100 11100110 10001111 10100001  ......
000000a8: 11100101 10011111 10111010 11100110 10011100 10101100  ......
000000ae: 11100111 10011010 10000100 11100101 10001010 10100000  ......
000000b4: 11101000 10100111 10100011 11100101 10101111 10000110  ......
000000ba: 11100110 10010110 10111001 11100110 10110011 10010101  ......
000000c0: 11100011 10000000 10000010 00001010                    ..
\end{lstlisting}
\par

对于怎么看上面的这一个数据流，其实与我们对于他处理，或者加密方法的是有关系的。通常我们其看为一个二进制数据流。\par

\section{基本概念}
我们用小写$m,c,k\ldots$表示二进制的位,$m$表示原始数据，$c$表示加密后数据，$k$表示密钥，大写E表示二进制的运算（也可称为函数、算子），那么对于一个流加密我们可以表示为$c_i=E(m_i,k_i)$,其中$i=0,1,2,\ldots$,i表示是第几位。我们可以看到流密码的核心就是设计E和密钥流$k_0,k_1,k_2,\ldots$。但是由于是位运算，E也没有什么好设计的(为什么?)，通常会用异或运算，异或运算好处是加解密都可以用这个运算。\par
\begin{table}[htbp]
	\centering
	\caption{"异或"运算/函数定义("异或"运算真值表)}
	\begin{tabular}{|c|c|c|}
		\hline
		x&y&$z=x\oplus y$\\
		\hline 
		0&0  &0  \\ 
		\hline 
		0&1  &1  \\ 
		\hline 
		1&0  &1  \\ 
		\hline 
		1& 1 & 0 \\ 
		\hline 
	\end{tabular} 
	\label{tab:xor-def}%
\end{table}
那么流密码的设计将归结为密钥的设计，就是设计如何产生一个密钥流$k_i=G(s) \ i=0,1,2,\ldots$,s是密钥产生的种子(seeds),也就是产生密钥流的一个初始值，G(generator)是密钥生成算法，可见s是整个算法的秘密。流密码的加解密可以写为：\par
\begin{equation}
	G(s)\oplus m_i =c_i 
\end{equation}
\begin{equation}	
	G(s)\oplus c_i =m_i 
\end{equation}
\section{密钥的产生}
根据香浓的完全安全系统的定义，如果密钥流是一个随机数，那么就可以构成一个完全安全加密系统，但是无法达到这个要求，所以通常我们会用伪随机数发生器PRG(pesudo-random generator )来产生密钥流。
\subsection{线性同余发生器LCG(linear congruential generator)}
可以利用$x_n=(ax_{n-1}+b) \ mod\ m$产生一个周期不超过m的伪随机数序列，$x_0$为种子(seed)，也就是密钥。\par
LCG不用在密码学中，因其在1977年被J.A.\ Reeds破译，也就是找到预测的方法，但是其在一些需要产生随机数的场合下依然有应用，比如一些在一些测试中。\par
下面我么实际给出一个例子，计算一下，使得大家有个直观感觉。\par
\begin{equation}
	x_n=2x_{n-1}+3 mod 307
\end{equation}
\begin{lstlisting}
	sage: b=67
	....: for i in range(0,307):
	....:     a=b
	....:     b=mod(2*a+3,307)
	....:     print i,":",b
	....:
\end{lstlisting}
我们看看上面这个线性同余方程所产生的序列：
\setlength{\columnsep}{1cm}%调整两列中间的距离
\setlength{\columnseprule}{1pt} 
\def \columnseprulecolor{\color{blue}}%定义分割线的颜色

\begin{multicols}{4}
	0 : 137\\
	1 : 277\\
	2 : 250\\
	3 : 196\\
	4 : 88\\
	5 : 179\\
	6 : 54\\
	7 : 111\\
	8 : 225\\
	9 : 146\\
	10 : 295\\
	11 : 286\\
	12 : 268\\
	13 : 232\\
	14 : 160\\
	15 : 16\\
	16 : 35\\
	17 : 73\\
	18 : 149\\
	19 : 301\\
	20 : 298\\
	21 : 292\\
	22 : 280\\
	23 : 256\\
	24 : 208\\
	25 : 112\\
	26 : 227\\
	27 : 150\\
	28 : 303\\
	29 : 302\\
	30 : 300\\
	31 : 296\\
	32 : 288\\
	33 : 272\\
	34 : 240\\
	35 : 176\\
	36 : 48\\
	37 : 99\\
	38 : 201\\
	39 : 98\\
	40 : 199\\
	41 : 94\\
	42 : 191\\
	43 : 78\\
	44 : 159\\
	45 : 14\\
	46 : 31\\
	47 : 65\\
	48 : 133\\
	49 : 269\\
	50 : 234\\
	51 : 164\\
	52 : 24\\
	53 : 51\\
	54 : 105\\
	55 : 213\\
	56 : 122\\
	57 : 247\\
	58 : 190\\
	59 : 76\\
	60 : 155\\
	61 : 6\\
	62 : 15\\
	63 : 33\\
	64 : 69\\
	65 : 141\\
	66 : 285\\
	67 : 266\\
	68 : 228\\
	69 : 152\\
	70 : 0\\
	71 : 3\\
	72 : 9\\
	73 : 21\\
	74 : 45\\
	75 : 93\\
	76 : 189\\
	77 : 74\\
	78 : 151\\
	79 : 305\\
	80 : 306\\
	81 : 1\\
	82 : 5\\
	83 : 13\\
	84 : 29\\
	85 : 61\\
	86 : 125\\
	87 : 253\\
	88 : 202\\
	89 : 100\\
	90 : 203\\
	91 : 102\\
	92 : 207\\
	93 : 110\\
	94 : 223\\
	95 : 142\\
	96 : 287\\
	97 : 270\\
	98 : 236\\
	99 : 168\\
	100 : 32\\
	101 : 67\\
	********\\
	102 : 137\\
	103 : 277\\
	104 : 250\\
	105 : 196\\
	106 : 88\\
	107 : 179\\
	108 : 54\\
	109 : 111\\
	110 : 225\\
	111 : 146\\
	112 : 295\\
	113 : 286\\
	114 : 268\\
	115 : 232\\
	116 : 160\\
	117 : 16\\
	118 : 35\\
	119 : 73\\
	120 : 149\\
	121 : 301\\
	122 : 298\\
	123 : 292\\
	124 : 280\\
	125 : 256\\
	126 : 208\\
	127 : 112\\
	128 : 227\\
	129 : 150\\
	130 : 303\\
	131 : 302\\
	132 : 300\\
	133 : 296\\
	134 : 288\\
	135 : 272\\
	136 : 240\\
	137 : 176\\
	138 : 48\\
	139 : 99\\
	140 : 201\\
	141 : 98\\
	142 : 199\\
	143 : 94\\
	144 : 191\\
	145 : 78\\
	146 : 159\\
	147 : 14\\
	148 : 31\\
	149 : 65\\
	150 : 133\\
	151 : 269\\
	152 : 234\\
	153 : 164\\
	154 : 24\\
	155 : 51\\
	156 : 105\\
	157 : 213\\
	158 : 122\\
	159 : 247\\
	160 : 190\\
	161 : 76\\
	162 : 155\\
	163 : 6\\
	164 : 15\\
	165 : 33\\
	166 : 69\\
	167 : 141\\
	168 : 285\\
	169 : 266\\
	170 : 228\\
	171 : 152\\
	172 : 0\\
	173 : 3\\
	174 : 9\\
	175 : 21\\
	176 : 45\\
	177 : 93\\
	178 : 189\\
	179 : 74\\
	180 : 151\\
	181 : 305\\
	182 : 306\\
	183 : 1\\
	184 : 5\\
	185 : 13\\
	186 : 29\\
	187 : 61\\
	188 : 125\\
	189 : 253\\
	190 : 202\\
	191 : 100\\
	192 : 203\\
	193 : 102\\
	194 : 207\\
	195 : 110\\
	196 : 223\\
	197 : 142\\
	198 : 287\\
	199 : 270\\
	200 : 236\\
	201 : 168\\
	202 : 32\\
	203 : 67\\
	204 : 137\\
	205 : 277\\
	206 : 250\\
	207 : 196\\
	208 : 88\\
	209 : 179\\
	210 : 54\\
	211 : 111\\
	212 : 225\\
	213 : 146\\
	214 : 295\\
	215 : 286\\
	216 : 268\\
	217 : 232\\
	218 : 160\\
	219 : 16\\
	220 : 35\\
	221 : 73\\
	222 : 149\\
	223 : 301\\
	224 : 298\\
	225 : 292\\
	226 : 280\\
	227 : 256\\
	228 : 208\\
	229 : 112\\
	230 : 227\\
	231 : 150\\
	232 : 303\\
	233 : 302\\
	234 : 300\\
	235 : 296\\
	236 : 288\\
	237 : 272\\
	238 : 240\\
	239 : 176\\
	240 : 48\\
	241 : 99\\
	242 : 201\\
	243 : 98\\
	244 : 199\\
	245 : 94\\
	246 : 191\\
	247 : 78\\
	248 : 159\\
	249 : 14\\
	250 : 31\\
	251 : 65\\
	252 : 133\\
	253 : 269\\
	254 : 234\\
	255 : 164\\
	256 : 24\\
	257 : 51\\
	258 : 105\\
	259 : 213\\
	260 : 122\\
	261 : 247\\
	262 : 190\\
	263 : 76\\
	264 : 155\\
	265 : 6\\
	266 : 15\\
	267 : 33\\
	268 : 69\\
	269 : 141\\
	270 : 285\\
	271 : 266\\
	272 : 228\\
	273 : 152\\
	274 : 0\\
	275 : 3\\
	276 : 9\\
	277 : 21\\
	278 : 45\\
	279 : 93\\
	280 : 189\\
	281 : 74\\
	282 : 151\\
	283 : 305\\
	284 : 306\\
	285 : 1\\
	286 : 5\\
	287 : 13\\
	288 : 29\\
	289 : 61\\
	290 : 125\\
	291 : 253\\
	292 : 202\\
	293 : 100\\
	294 : 203\\
	295 : 102\\
	296 : 207\\
	297 : 110\\
	298 : 223\\
	299 : 142\\
	300 : 287\\
	301 : 270\\
	302 : 236\\
	303 : 168\\
	304 : 32\\
	305 : 67\\
	306 : 137\\
\end{multicols}
\par

\subsection{线性反馈移位寄存器LSFR(Linear Feedback shift register)}
线性反馈移位寄存器可以有图形化表示方法，如\ref{lfsr-fig-example}:\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{LFSR-EXAMPLE.jpg}
	\caption{LFSR的图形化表示}
	\label{lfsr-fig-example}
\end{figure}
也有用逻辑电路图来表示，如\ref{lfsr-register}：\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{LFSR-REG-EXAMPLE.png}
	\caption{LFSR的逻辑电路图表示}
	\label{lfsr-register}
\end{figure}
也可以用一元多项式来表示，如：$x^4+x^3+x+1$。假设初始状态为1111，从最高位引出输出，我们可以实际看看内部状态和输出的变换序列。\par
而对于同样有四个寄存器，如果配置方式为$x^4+x^3+1$，假设初始状态也为1111，也是从最高位引出输出，我们可以实际看看内部状态和输出的变换序列，并于上面的结果进行比较。你会发现他的周期短。\par
\centerline{\textcolor{red}{\bfseries 我们当前希望在一定的资源配置下，能够得到周期最长的伪随机序列。}}

\section{序列的伪随机性}
我们知道流密码的安全性取决于密钥流的“安全性”，密钥流的安全性就是指其不易被破解，也就是是有良好的随机性，那么什么是“好的随机性”？\par
\begin{definition}{序列的自相关函数}
	GF(2)上的周期为T的序列${a_i}$的自相关函数为
	\begin{equation}
		R(\tau) =  \frac{1}{T}\sum_{k=1}^{T}(-1)^{a_k}(-1)^{a_{k+\tau}},0\leq \tau \leq T-1
	\end{equation}
\end{definition}
我们知道$(-1)^1 =-1,(-1)^0 =1,(-1)^1(-1)^1=1,(-1)^0(-1)^0=1,(-1)^1(-1)^0=-1$,所以有$a_k=a_{k+\tau}$时,$(-1)^{a_k}(-1)^{a_{k+\tau}}=1$,$a_k\neq a_{k+\tau}$时,$(-1)^{a_k}(-1)^{a_{k+\tau}}=-1$,也就是说将序列${a_i}$向后移动$\tau$形成一个新序列，然后这两个序列按上面的公式计算，数字越大，表示不同的比特越多，越小，表示相同的比特越多。\par

Golomb提出了伪随机周期序列应该满足3个随机性公设\cite{yang-mcry}：
\begin{enumerate}
	\item 在序列的一个周期内，0与1的个数相差最多为1.
	\item 在序列的一个周期内，长为1的游程占游程总数的$\frac{1}{2}$，长为2的游程占游程总数的$\frac{1}{2^2}$，\ldots,长为i的游程占游程总数的$\frac{1}{2^i}$，\ldots，且在等长的游程中0的游程个数与1的游程个数相等。
	\item 异自相关函数时一个常数。
\end{enumerate}
第一个公设说明序列${a_i}$中0和1出现的概论基本上相同，第二个公设说明0与1在序列中每一个位置上出现的概率相同，公设三表示，通过对序列与其平移后的序列进行比较，不能给出其他任何信息。\par
从密码系统的角度看，伪随机序列还应满足以下条件\cite{yang-mcry}：
\begin{enumerate}
	\item ${a_i}$的周期相当大。
	\item ${a_i}$的确定在计算上时容易的。
	\item 由密文和相应的明文的部分信息，不能确定整个密钥序列${a_i}$。
\end{enumerate}

\section{非线性序列}
为了使得密钥流更加随机，可使用多个LFSR来构造序列生成器，这多个LFSR的输出可以做为一个非线性组合函数的输入，新的序列生成器产生的序列周期应该尽可能大，但是从理论上可以证明新序列的周期不会大于各LFSR周期的成绩。
\subsection{Geff发生器}
三个LFSR产生的输出分别为$a^1,a^2,a^3$，在t时刻的输出记为$a_t^1,a_t^2,a_t^3$，Geff的t时刻输出为$b_t = (a_t^1\wedge a_t^2)\oplus (\neg a_t^1 \wedge a_t^3)$.